package solution;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-04-06
 * Time: 17:20
 */

//https://leetcode.cn/problems/combination-sum-iv/description/
class Solution3 {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        //Solution2,对比着看
        //顺序不同的序列被视作不同的组合
        //背包容量在外层
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}
